/***************************************************************************************
* Copyright (c) 2014-2022 Zihao Yu, Nanjing University
*
* NEMU is licensed under Mulan PSL v2.
* You can use this software according to the terms and conditions of the Mulan PSL v2.
* You may obtain a copy of Mulan PSL v2 at:
*          http://license.coscl.org.cn/MulanPSL2
*
* THIS SOFTWARE IS PROVIDED ON AN "AS IS" BASIS, WITHOUT WARRANTIES OF ANY KIND,
* EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO NON-INFRINGEMENT,
* MERCHANTABILITY OR FIT FOR A PARTICULAR PURPOSE.
*
* See the Mulan PSL v2 for more details.
***************************************************************************************/

#include "debug.h"
#include "memory/paddr.h"
#include <isa.h>

/* We use the POSIX regex functions to process regular expressions.
 * Type 'man regex' for more information about POSIX regex functions.
 */
#include <regex.h>
#include <stdbool.h>
#include <stdint.h>

enum {
  TK_NOTYPE = 256, TK_EQ, TK_IN, TK_HN, TK_RG, TK_NEQ, TK_AND, TK_DEREF
};

static struct rule {
  const char *regex;
  int token_type;
} rules[] = {

  {" +", TK_NOTYPE},    // spaces
  {"\\+", '+'},         // plus
  {"==", TK_EQ},        // equal
  {"-", '-'},           // substract
  {"\\*", '*'},       	// multiply
  {"/", '/'},         	// divide
  {"\\(", '('},       	// left parenthesis
  {"\\)", ')'},       	// right parenthesis
  {"0x[0-9a-f]+", TK_HN},    // hexadecimal integer
  {"[0-9]+", TK_IN},    // decimal integer
  {"\\$[0-9a-z\\$]+", TK_RG},     // reg_name 
  {"!=", TK_NEQ},    	// not equal 
  {"&&", TK_AND},    	// and  
};

#define NR_REGEX ARRLEN(rules)

static regex_t re[NR_REGEX] = {};

/* Rules are used for many times.
 * Therefore we compile them only once before any usage.
 */
void init_regex() {
  int i;
  char error_msg[128];
  int ret;

  for (i = 0; i < NR_REGEX; i ++) {
    ret = regcomp(&re[i], rules[i].regex, REG_EXTENDED);
    if (ret != 0) {
      regerror(ret, &re[i], error_msg, 128);
      panic("regex compilation failed: %s\n%s", error_msg, rules[i].regex);
    }
  }
}

typedef struct token {
  int type;
  char str[32];
} Token;

//                  32
static Token tokens[32] __attribute__((used)) = {};
static int nr_token __attribute__((used))  = 0;

static bool make_token(char *e) {
  int position = 0;
  int i;
  regmatch_t pmatch;

  nr_token = 0;

  while (e[position] != '\0') {
    /* Try all rules one by one. */
    for (i = 0; i < NR_REGEX; i ++) {
      if (regexec(&re[i], e + position, 1, &pmatch, 0) == 0 && pmatch.rm_so == 0) {
        char *substr_start = e + position;
        int substr_len = pmatch.rm_eo;

        /*Log("match rules[%d] = \"%s\" at position %d with len %d: %.*s",*/
            /*i, rules[i].regex, position, substr_len, substr_len, substr_start);*/

        position += substr_len;

        switch (rules[i].token_type) {
		  case TK_NOTYPE: break;
		  case '+': 
		  case '-': 
		  case '*':
		    if (nr_token == 0 || tokens[nr_token-1].type == '+' || tokens[nr_token-1].type == '-' || \
				tokens[nr_token-1].type == '*' || tokens[nr_token-1].type == '/' || \
				tokens[nr_token-1].type == TK_EQ || tokens[nr_token-1].type == TK_NEQ) {
			  tokens[nr_token++].type = TK_DEREF;
			  break;
			}
		  case '/':
		  case '(':
		  case ')':
		  case TK_EQ: 
		  case TK_NEQ: 
		  case TK_AND: 
			tokens[nr_token++].type = rules[i].token_type;
			break;
		  case TK_IN:
		  case TK_HN:
		  case TK_RG:
			tokens[nr_token].type = rules[i].token_type;

			/* move integer/hexadecimal number/reg name to tokens[nr_token].str */
			for(int j = 0; j < substr_len; j ++) {
			  tokens[nr_token].str[j] = substr_start[j];
			}
			tokens[nr_token++].str[substr_len] = '\0';

			break; 
          default: TODO();
        }

        break;
      }
    }

    if (i == NR_REGEX) {
      printf("no match at position %d\n%s\n%*.s^\n", position, e, position, "");
      return false;
    }
  }

  return true;
}

uint32_t eval(int p, int q, bool *valid);

word_t expr(char *e, bool *success) {
  if (!make_token(e)) {
    *success = false;
    return 0;
  }

  return eval(0, nr_token - 1, success);
}

bool check_parentheses(int p, int q, bool *valid) {
  int num = 0; 
  bool flag = true;  	// 表达式两边是否被括号包围

  if (tokens[p].type != '(' || tokens[q].type != ')')
	flag = false;

  /* 判断表达式中的括号是否匹配 */
  for (int i = p; i <= q; i++) {
	if (tokens[i].type == '(') num++;
	if (tokens[i].type == ')') {
	  num --;
	  if (num < 0) { 	// 表达式中的括号不匹配
		break;
 	  }
	  if (num == 0 && i != q) flag = false;
	}
  }
  
  // 表达式中的括号不匹配
  if (num != 0) {
    *valid = false;
    flag = false;
  }

  return flag;
}

uint32_t eval(int p, int q, bool *valid) {
  bool expr_valid = true; 	// 表达式是否有效

  if (p > q) {
    /* Bad expression */
	panic("Bad expression");
  }
  else if (p == q) {
	/*if (tokens[p].type != TK_IN) panic("Bad expression--");*/

	/* convert expr to number */
	uint32_t N = 0;

	if (tokens[p].type == TK_IN) {
	  sscanf(tokens[p].str, "%u", &N);
	}
	else if (tokens[p].type == TK_HN) {
	  sscanf(tokens[p].str, "%x", &N);
	}
	else {
	  N = isa_reg_str2val(tokens[p].str + 1, valid);
	}

	return N;
  }
  else if (check_parentheses(p, q, &expr_valid) == true) {
    return eval(p + 1, q - 1, valid);
  }
  else {
	if (expr_valid == true) {

  	  /* 获取主运算符的位置 */
  	  int op_priority;    // 优先级, 0: && ; 1: == and !=;  2:+ and -; 3: * and /; 4: *(dereference)
  	  int op = p;
  	  int flag = 0;     		// 标志是否遇到左括号
  
  	  op_priority = 100; // 置为比4大的数
  
  	  if (tokens[op].type == TK_AND) {
  	    op_priority = 0;
  	  }
  	  if (tokens[op].type == TK_EQ || tokens[op].type == TK_NEQ) {
  	    op_priority = 1;
  	  }
  	  if (tokens[op].type == '+' || tokens[op].type == '-') {
  	    op_priority = 2;
  	  }
	  if (tokens[op].type == '*' || tokens[op].type == '/') {
  	    op_priority = 3;
  	  }
	  if (tokens[op].type == TK_DEREF) {
  	    op_priority = 4;
  	  }

	  if (tokens[op].type == '(') flag ++;
  
  	  for (int i = op + 1; i <= q; i ++) {
  	    if (!flag) { 			// 没有遇到过左括号

  	      if (tokens[i].type == TK_AND) {
  	  	    if (op_priority >= 0 ) {
			  op = i;
			  op_priority = 0;
		    }
  	      }

  	      if (tokens[i].type == TK_EQ || tokens[i].type == TK_NEQ) {
  	  	    if (op_priority >= 1) {
			  op = i;
			  op_priority = 1;
		    }
  	      }

  	      if (tokens[i].type == '+' || tokens[i].type == '-') {
  	  	    if (op_priority >= 2 ) {
			  op = i;
			  op_priority = 2;
		    }
  	      }
  
  	      if (tokens[i].type == '*' || tokens[i].type == '/') {
  	  	    if (op_priority >= 3) {
			  op = i;
			  op_priority = 3;
		    }
  	      }

  	      if (tokens[i].type == TK_DEREF) {
  	  	    if (op_priority >= 4) {
			  op = i;
			  op_priority = 4;
		    }
  	      }
  
  	  	if (tokens[i].type == '(') flag ++; // 遇到左括号
  	    }
  	    else { 				// 遇到过左括号	
  	  	  if (tokens[i].type == '(') flag ++; // 遇到左括号
  	  	  if (tokens[i].type == ')') flag --;  // 遇到右括号
  	    }
  	  }

	  if (tokens[op].type == TK_DEREF) {
		uint32_t val = eval(op + 1, q, valid);

		if (val < 0x80000000) {
		  *valid = false;

		  return 0;
		}

		return *guest_to_host(val);
	  }

  	  uint32_t val1 = eval(p, op - 1, valid);
  	  uint32_t val2 = eval(op + 1, q, valid);

  	  switch (tokens[op].type) {
		case '+': return val1 + val2; break;
  	    case '-': return val1 - val2; break;
  	    case '*': return val1 * val2; break;
  	    case '/': return val1 / val2; break;
		case TK_EQ: return val1 ==  val2 ? 1 : 0; break;
		case TK_NEQ: return val1 !=  val2 ? 1 : 0; break;
		case TK_AND: return val1 &&  val2 ? 1 : 0; break;
  	    default: assert(0);
  	  }
    }
	else {
	  *valid = false;
	}
  }

  return 0;
}
